home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / MCASM.RAR / MC_ASM.EXE / WROX_ASM / CH10 / PROGRAMS / ARIF.C < prev    next >
C/C++ Source or Header  |  1994-05-30  |  7KB  |  307 lines
  1. #include <stdio.h>
  2. #include <process.h>
  3. // The number of bits in "register"
  4. #define BITS_IN_REGISTER 16
  5. // The top value in register
  6. #define TOP_VALUE (((long) 1<<BITS_IN_REGISTER)-1)
  7. // The ranges
  8. #define FIRST_QTR (TOP_VALUE/4+1)
  9.  
  10. #define HALF (2*FIRST_QTR)
  11.  
  12. #define THIRD_QTR (3*FIRST_QTR)
  13. // The number of symbols in alfabet
  14. #define NO_OF_CHARS 256
  15. // End Of File symbol
  16. #define EOF_SYMBOL (NO_OF_CHARS+1)
  17. // Total number of symbols
  18. #define NO_OF_SYMBOLS (NO_OF_CHARS+1)
  19. // The limit of frequency for scale
  20. #define MAX_FREQUENCY 16383
  21. // The tables for recoding
  22. unsigned char index_to_char[NO_OF_SYMBOLS];
  23. int char_to_index[NO_OF_CHARS];
  24. // The table of frequency
  25. int cum_freq[NO_OF_SYMBOLS+1];
  26. int freq[NO_OF_SYMBOLS+1];
  27. // The registers of limit
  28. long low,high;
  29. // The register of code
  30. long value;
  31. // Registers for bit i/o
  32. long bits_to_follow;
  33. int buffer;
  34. int bits_to_go;
  35. int garbage_bits;
  36.  
  37. int counteri,countero;
  38.  
  39. void start_model(void)
  40. {
  41.     int    i;
  42.     for (i=0;i<NO_OF_CHARS;i++)
  43.     {
  44.         char_to_index[i]=i+1;
  45.         index_to_char[i+1]=i;
  46.     }
  47.     for (i=0;i<=NO_OF_SYMBOLS;i++)
  48.     {
  49.         freq[i]=1;
  50.         cum_freq[i]=NO_OF_SYMBOLS-i;
  51.     }
  52.     freq[0]=0;
  53. }
  54. // Reinitialization of model by next char
  55. void update_model (int symbol)
  56. {
  57.     int    i;
  58.     int    ch_i,ch_symbol;
  59.     int    cum;
  60. // Check the counter of frequency for overflow
  61.     if (cum_freq[0]==MAX_FREQUENCY)
  62.     {
  63.         cum=0;
  64. // Update the frequences duaring the overflow
  65.         for (i=NO_OF_SYMBOLS;i>=0;i--)
  66.         {
  67.             freq[i]=(freq[i]+1)/2;
  68.             cum_freq[i]=cum;
  69.             cum+=freq[i];
  70.         }
  71.     }
  72.     for(i=symbol;freq[i]==freq[i-1];i--);
  73.     if (i<symbol)
  74.     {
  75.         ch_i=index_to_char[i];
  76.         ch_symbol=index_to_char[symbol];
  77.         index_to_char[i]=ch_symbol;
  78.         index_to_char[symbol]=ch_i;
  79.         char_to_index[ch_i]=symbol;
  80.         char_to_index[ch_symbol]=i;
  81.     }
  82. // Update the values in the tables of frequencies
  83.     freq[i]+=1;
  84.     while(i>0)
  85.     {
  86.         i-=1;
  87.         cum_freq[i]+=1;
  88.     }
  89. }
  90. // Initialization of bits output
  91. void start_inputing_bits(void)
  92. {
  93.     bits_to_go=0;
  94.     garbage_bits=0;
  95. }
  96. // Input the next bit of compressed information
  97. int input_bit(char *buffi,int lengi)
  98. {
  99.     int t;
  100.     if(bits_to_go==0)
  101.     {
  102.         buffer=(unsigned char) buffi[counteri++];
  103.         if(counteri==lengi)
  104.         {
  105.             garbage_bits+=1;
  106.             if(garbage_bits>BITS_IN_REGISTER-2)
  107.             {
  108.                 printf("Error in compressed file\n");
  109.                 exit(-1);
  110.             }
  111.         }
  112.         bits_to_go=8;
  113.     }
  114.     t=buffer & 1;
  115.     buffer>>=1;
  116.     bits_to_go-=1;
  117.     return t;
  118. }
  119. // Initialization of bits output
  120. void start_outputing_bits (void)
  121. {
  122.     buffer=0;
  123.     bits_to_go=8;
  124. }
  125. // Input the next bit of compressed information
  126. void output_bit(int bit, char *buffo, int lengo)
  127. {
  128.     buffer>>=1;
  129.     if(bit)
  130.         buffer |=0x80;
  131.     bits_to_go-=1;
  132.     if(bits_to_go==0)
  133.     {
  134.         buffo[countero++]=(unsigned char) buffer;
  135.         if (countero==lengo+1) {
  136.             printf("Overflow the output buffer.\n");
  137.             return;
  138.         }
  139.         bits_to_go=8;
  140.     }
  141. }
  142. // Clear the bits output
  143. void done_outputing_bits(char *buffo, int lengo)
  144. {
  145.     buffo[countero++]=(unsigned char) (buffer>>bits_to_go);
  146.     if (countero==lengo+1) {
  147.         printf("Overflow the output buffer.\n");
  148.         return;
  149.     }
  150. }
  151. // Output the current bit and other bits
  152. void output_bit_plus_follow(int bit, char *buffo, int lengo)
  153. {
  154.     output_bit(bit,buffo,lengo);
  155.     while(bits_to_follow>0)
  156.     {
  157.         output_bit(!bit,buffo,lengo);
  158.         bits_to_follow--;
  159.     }
  160. }
  161. // Initialization of registers of limits and code before compression
  162. void start_encoding(void)
  163. {
  164.     low=0l;
  165.     high=TOP_VALUE;
  166.     bits_to_follow=0l;
  167. }
  168. // Clear the bits output
  169. void done_encoding(char *buffo,int lengo)
  170. {
  171.     bits_to_follow++;
  172.     if(low<FIRST_QTR)
  173.         output_bit_plus_follow(0,buffo,lengo);
  174.     else
  175.         output_bit_plus_follow(1,buffo,lengo);
  176. }
  177. // Initialization of registers before decompression
  178. // Load the begin of compressed information
  179. void start_decoding(char *buffi,int lengi)
  180. {
  181.     int    i;
  182.     value=0l;
  183.     for (i=1;i<=BITS_IN_REGISTER;i++)
  184.         value=2*value+input_bit(buffi,lengi);
  185.     low=0l;
  186.     high=TOP_VALUE;
  187. }
  188. // Coding the next char
  189. void encode_symbol(int symbol,char *buffo,int lengo)
  190. {
  191.     long range;
  192.     // Update the ranges and limits
  193.     range=(long)(high-low)+1;
  194.     high=low+(range*cum_freq[symbol-1])/cum_freq[0]-1;
  195.     low=low+(range*cum_freq[symbol])/cum_freq[0];
  196.     while(1)
  197.     {
  198.         if(high<HALF)
  199.             output_bit_plus_follow(0,buffo,lengo);
  200.         else if (low>=HALF)
  201.         {
  202.             output_bit_plus_follow(1,buffo,lengo);
  203.             low-=HALF;
  204.             high-=HALF;
  205.         }
  206.         else if(low>=FIRST_QTR && high<THIRD_QTR)
  207.         {
  208.             bits_to_follow+=1;
  209.             low-=FIRST_QTR;
  210.             high-=FIRST_QTR;
  211.         }
  212.         else
  213.             break;
  214.         // Shift to left with shift the next bit
  215.         low=2*low;
  216.         high=2*high+1;
  217.     }
  218. }
  219. // Decoding the next symbol
  220. int decode_symbol(char *buffi,int lengi)
  221. {
  222.     long range;
  223.     int cum,symbol;
  224.     // Calculating the current scale of frequencies
  225.     range=(long)(high-low)+1;
  226.     // Scaling the values in register of code
  227.     cum=(int) ((((long)(value-low)+1)*cum_freq[0]-1)/range);
  228.     // Search the symbol in  the table of symbols
  229.     for(symbol=1;cum_freq[symbol]>cum;symbol++);
  230.     // Recalculating the limits
  231.     high=low+(range*cum_freq[symbol-1])/cum_freq[0]-1;
  232.     low=low+(range*cum_freq[symbol])/cum_freq[0];
  233.     // Delete the current symbol from input flow
  234.     while(1)
  235.     {
  236.         if(high<HALF)
  237.         {
  238.         }
  239.         else if (low>=HALF)
  240.         {
  241.             value-=HALF;
  242.             low-=HALF;
  243.             high-=HALF;
  244.         }
  245.         else if (low>=FIRST_QTR && high<THIRD_QTR)
  246.         {
  247.             value-=FIRST_QTR;
  248.             low-=FIRST_QTR;
  249.             high-=FIRST_QTR;
  250.         }
  251.         else
  252.             break;
  253.         // Shift to left with shift the next bit
  254.         low=2*low;
  255.         high=2*high+1;
  256.         value=2*value+input_bit(buffi,lengi);
  257.     }
  258.     return symbol;
  259. }
  260. // Adaptive arifmetic compression
  261. int arif_encode (char *buffi,int lengi,char *buffo,int lengo)
  262. {
  263.     int ch,symbol;
  264.     counteri=0;
  265.     countero=0;
  266.     start_model();
  267.     start_outputing_bits();
  268.     start_encoding();
  269.     while(1)
  270.     {
  271.         ch=((unsigned char) buffi[counteri++]);
  272.         symbol=char_to_index[ch];
  273.         encode_symbol(symbol,buffo,lengo);
  274.         update_model(symbol);
  275.         if (counteri==lengi)
  276.             break;
  277.     }
  278.     encode_symbol(EOF_SYMBOL,buffo,lengo);
  279.     done_encoding(buffo,lengo);
  280.     done_outputing_bits(buffo,lengo);
  281.     return countero;
  282. }
  283. // Adaptive arifmetic decompression
  284. int arif_decode (char *buffi, int lengi, char *buffo, int lengo)
  285. {
  286.     int ch,symbol;
  287.     counteri=0;
  288.     countero=0;
  289.     start_model();
  290.     start_inputing_bits();
  291.     start_decoding(buffi,lengi);
  292.     while(1)
  293.     {
  294.         symbol=decode_symbol(buffi,lengi);
  295.         if(symbol==EOF_SYMBOL)
  296.             break;
  297.         ch=index_to_char[symbol];
  298.         buffo[countero++]=(unsigned char) ch;
  299.         if (countero==lengo+1) {
  300.             printf("Overflow the output buffer.\n");
  301.             break;
  302.         }
  303.         update_model(symbol);
  304.     }
  305.     return countero;
  306. }
  307.